package com.linkai.linklist;

import java.util.List;

/**
 * @Description: 反转链表
 * @Author: 林凯
 * @Date: 2021/10/8 9:31
 */
public class JZ15 {
    public static void main(String[] args) {

    }
    public ListNode ReverseList(ListNode head) {
        /*
            思路：利用“头插法”反转链表
                需要建立一个新的链表（新，旧链表都是不带头结点的）
        * */

        if (head == null) {
            return head;
        }
        ListNode newListHead = new ListNode(head.val);
        ListNode tmp = head.next;
        while (tmp != null) {
            ListNode newNode = new ListNode(tmp.val);
            newNode.next = newListHead;
            newListHead = newNode;
            // 移动遍历链表的指针
            tmp = tmp.next;
        }
        return newListHead;
    }
}
